// 链表比数组占用更多的内存空间
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
/**
 * 初始化链表
 */
const n0 = new ListNode(0);
const n1 = new ListNode(1);
const n2 = new ListNode(2);
const n3 = new ListNode(3);
const n4 = new ListNode(4);
const n5 = new ListNode(5);
// 构建节点之间的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;

/**
 * 在链表的节点 n0 之后插入节点 P
 * @param n0 链表的头节点
 * @param P 
 */
function ListInsert(n0: ListNode, P: ListNode) {
  const n1 = n0.next;
  P.next = n1;
  n0.next = P;
}

/**
 * 删除链表节点
 * @param n0 链表的头节点
 * @returns 
 */
function ListRemove(n0: ListNode): void {
  if (n0.next === null) {
    return;
  }
  const P = n0.next;
  const n1 = P.next;
  n0.next = n1;
}
/**
 * 访问链表中索引为 index 的节点
 * @param head 链表的头节点
 * @param index  索引值
 * @returns  索引为 index 的节点
 */
function access(head: ListNode | null, index: number): ListNode | null {
  for (let i = 0; i < index; i++) {
    if (!head) {
      return null;
    }
    head = head?.next;
  }
  return head;
}
/**
 *  查找链表中值为 target 的节点
 * @param head 链表的头节点
 * @param target  目标值
 * @returns  目标值在链表中的索引，如果不存在则返回 -1
 */
function LinkFind(head: ListNode | null, target: number): number {
  let index = 0;
  while (head !== null) {
    if (head.val === target) {
      return index;
    }
    head = head.next;
    index += 1;
  }
  return -1;
}